package com.chenken;


/**
 *	最长上升子序列（LIS）
 *	子序列:不连续
 *  https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class LongestIncreasingSequence {

	/**
	 * dp[i]是以nums[i]结尾的最长上升子序列的长度，初始值为1
	 * 
	 */
	public static int lengthOfLIS1(int[] nums) {
		if(nums == null || nums.length == 0) {
			return 0;
		}
		int[] dp = new int[nums.length];
		int max = dp[0] = 1;
		for(int i = 1;i < dp.length;i++) {
			dp[i] = 1;
			for(int j = 0;j < i;j++) {
				//	判断nums[i]是否能接在nums[j]后面
				if(nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i],dp[j] + 1);
				}
			}
			max = Math.max(dp[i],max);
		}
		return max; 
	}
	
	/**
	 * 	总是把比牌顶元素大的放后面
	 * 	二分搜索
	 *  	思路：假设数组是nums,也就是最初的牌数组
	 *  	top[i]是第i个排队的牌顶，len是牌堆的数量，初始值为0
	 *  	遍历每一张牌num
	 *  	利用二分搜索找出num最终要放入的牌堆位置index
	 *  	num作为第index个牌堆的牌顶，top[index] = num
	 *  	如果index等于len,相当于新建一个牌堆,牌堆数量+1,也就是len++
	 */
	public static int lengthOfLIS2(int[] nums) {
		if(nums == null || nums.length == 0) {
			return 0;
		}
		//	牌顶数组
		int[] top = new int[nums.length];
		//	牌组数量
		int len = 0;
		for(int num:nums) {
			int index = 0;
			for(int i = 0;i<len;i++) {
				//	如果这张牌小于牌顶元素,替换牌顶元素
				if(num <= top[i]) {
					top[i] = num;
				}else {
					index++;//索引位置++
				}
			}
			//	索引位置值 = len，新建牌堆
			if(index == len) {
				top[index] = num;//在该索引处放入这张牌
				len++;//牌组数量+1
			}
		}
		return len; 
	}
	
	/**
	 * 	总是把比牌顶元素大的放后面
	 * 	二分搜索
	 *  	思路：假设数组是nums,也就是最初的牌数组
	 *  	top[i]是第i个排队的牌顶，len是牌堆的数量，初始值为0
	 *  	遍历每一张牌num
	 *  	利用二分搜索找出num最终要放入的牌堆位置index
	 *  	num作为第index个牌堆的牌顶，top[index] = num
	 *  	如果index等于len,相当于新建一个牌堆,牌堆数量+1,也就是len++
	 */
	public static int lengthOfLIS3(int[] nums) {
		if(nums == null || nums.length == 0) {
			return 0;
		}
		//	牌顶数组
		int[] top = new int[nums.length];
		//	牌组数量
		int len = 0;
		for(int num:nums) {
			//	找到这张牌应该存在的索引位置
			int index = binarySearch(top,num,len);		
			//	覆盖牌顶或新建牌堆
			top[index] = num;
			//	表示索引位置为len,牌堆数量+1
			if(index == len) {
				len++;
			}
		}
		return len; 
	}
	
	/**
	 * 	二分搜索，查找元素插入位置
	 * {5,7,8,9,10}	6
	 * @param nums
	 * @param num
	 * @return
	 */
	private static int binarySearch(int top[],int num,int len) {
		int begin = 0;
		int end = len;
		while(begin < end) {
			int mid = (begin + end) >> 1;
			if(num <= top[mid]) {
				end = mid;
			}else {
				begin = mid + 1;
			}
		}		
		return begin;		
	}
	
	public static void main(String[] args) {
		int[] nums = {10,2,2,5,1,7,101,18,19};
		System.out.println(lengthOfLIS1(nums));
		System.out.println(lengthOfLIS2(nums));
		System.out.println(lengthOfLIS3(nums));
	}
}
